//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1]
//输出：[[0,1],[1,0]]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1]
//输出：[[1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 6 
// -10 <= nums[i] <= 10 
// nums 中的所有整数 互不相同 
// 
// Related Topics 数组 回溯 👍 2061 👎 0


package com.cjl.leetcode.editor.cn;

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;

import java.util.*;

/**
 * [P46]_全排列
 *
 * @author cjl
 * @date 2022-06-11 17:41:49
 */
public class P46_Permutations {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P46_Permutations().new Solution();
        solution.permute(new int[]{1,2,3}).stream().forEach(a-> System.out.println("args = " + Arrays.deepToString(a.toArray())));
    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解题思路：回溯法
         * @param nums
         * @return
         */
//        public List<List<Integer>> permute(int[] nums) {
//            List<List<Integer>> resList = new ArrayList<>();
//            List<Integer> curList = new ArrayList<>();
//            for(int i = 0 ; i< nums.length; i++){
//                curList.add(nums[i]);
//            }
//            list(curList, nums.length, 0, resList);
//            return resList;
//        }
//
//        /**
//         *
//         * @param curList 当前列表
//         * @param all   list总大小
//         * @param curr  已使用数字位置
//         * @param resList 结果集
//         */
//        private void list(List<Integer> curList, int all,  int curr, List<List<Integer>> resList){
//            if(all == curr){
//                resList.add(new ArrayList<>(curList));
//            }
//            for(int i = curr ; i < all ; i++){
//                //[1,2,3,4] , curr = 1, 表示第1个位置之后第元素都没有使用过，交换后，curlist前2个元素就是使用都元素，后面是未使用都，递归遍历
//                Collections.swap(curList, i , curr);
//                list(curList, all ,curr +1, resList);
//                Collections.swap(curList, i , curr);
//            }
//        }

        public List<List<Integer>> permute(int[] nums){
            List<List<Integer>> resList = new ArrayList<>();
            List<Integer> currList = new ArrayList<>();
            for(int i =0; i < nums.length; i++){
                currList.add(nums[i]);
            }
            pailie(resList,currList, nums.length, 0);
            return resList;
        }

        public void pailie(List<List<Integer>> resList, List<Integer> currList, int all, int curr){
            if(all == curr){
                resList.add(new ArrayList<>(currList));
            }
            for(int i = curr; i< all; i++){
                Collections.swap(currList, curr, i);
                pailie(resList, currList, all, curr+1);
                Collections.swap(currList, curr, i);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}